package com.Questions.DP;


/**
 * 判断子序列
 */
public class leetcode392 {
    // 双指针 解法
//    public boolean isSubsequence(String s, String t) {
//        // 判断s是否是t的子序列
//        int n=s.length(),m=t.length();
//        int i=0;
//        int j=0;
//        while(i<n&&j<m){
//            if(s.charAt(i)==t.charAt(j)){
//                i++;
//            }
//            j++;
//        }
//        // 如果是子序列 那么i一定能遍历到字符串末尾
//        return i==n;
//    }

    // 时间复杂度O(m+n)
    // 空间复杂度O(1)

    // DP

    public boolean isSubsequence(String s, String t) {
        // 考虑双指针解法 在寻找到上一个匹配的字符之后
        // 还要依次寻找下一个 匹配的字符
        // 动态规划算法 维护一个二维数组 存储某个字符第一次出现的位置
        // 实现在t中 实现跳跃遍历
        int n = s.length(), m = t.length();

        int[][] f = new int[m + 1][26];
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
            // 26个字母 初始化 将其第一次出现的位置 设置为最大值
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) == j + 'a')//如果j字符出现在了i位置 那么将其第一次出现的位置更新为i
                    f[i][j] = i;
                else// 此位置并没有出现j字符 所以和后面一个单元的状态一样
                    f[i][j] = f[i + 1][j];
            }
        }
        int add = 0;// 从add开始寻找s中字符对应的值
        for (int i = 0; i < n; i++) {
            if (f[add][s.charAt(i) - 'a'] == m) {// 在s在i位置的字符在f中没有出现
                return false;
            }// 将 add直接 更新为 已经寻找到的字符的后一位
            add = f[add][s.charAt(i) - 'a'] + 1;
        }
        return true;
    }

    // 时间复杂度 O(m*26 +n)
    //


}
